library LinkedList
//==============================================================================
//  LinkedList script by Ammorth - Version 1.2b - February 2, 2010
//==============================================================================
//
//  用途:
//      - 为VJ添加链表功能.
//
//  涉及:
//      - 储存数据到一个双向链表中,使用户能轻松地添加与移除链表中任何位置的数据.
//      - Stores data in a doubly-linked list, allowing one to add and remove
//      data easily anywhere within the list.
//
//  用法:
//      - Create a new empty list                       List.create()                  (-> List)
//        新建一个空的链表
//      - Add new data to the front of the list         Link.createBefore(list, data)  (-> Link)
//        添加一个新数据到链表头
//      - Add new data to the back of the list          Link.create(list, data)        (-> Link)
//        添加一个新数据到链表尾
//      - Insert new data before a link                 link.insertBefore(data)        (-> Link)
//        在节点之前插入一个新数据
//      - Insert new data after a link                  link.insert(data)              (-> Link)
//        在节点之后插入一个新数据
//      - Get the data of a link                        link.data                      (-> integer)
//        获取链表的数据
//      - Get the next or previous links                link.next / link.prev          (-> Link)
//        获取链表的下一个或前一个节点
//      - Get the list a link belongs to                link.parent                    (-> List)
//        获取链表所属
//      - Get the first or last link in a list          list.first / list.last         (-> Link)
//        获取链表的头或尾节点
//      - Get the size of a list                        list.size                      (-> integer)
//        获取链表的尺寸
//      - Get the link which contains data              list.search(data)              (-> Link)
//        获取含有data数据的节点
//      - Remove a link                                 link.destroy()
//        移除一个节点
//      - Clear the entire list (including links)       list.clear()
//        清空整个链表(包括节点)
//      - Destroy the entire list (including links)     list.destroy()
//        移除整个链表(包括节点)
//
//  注意:
//      - If you find you are creating large lists, or that you are using them
//      to store long-term data, you can increase the number of links avaliable,
//      with a slight hit to performance (default is 8190).
//      - The number of lists avaliable is set at 8190.  If you need more, you
//      need a better approach at managing data.
//      - Except for the data, all variables are read-only (don't try and use
//      the 'x' versions).
//      如果你发现你正在创建一个超大的链表,或者你使用它们去存储一些长期存在的数据,
//      你可以增加链表变量的数量,用一种柔和的方式.(默认是8190)
//      -链表变量的设计尺寸为8190.如果你需要更多,那你就需要一个更好的管理数据的方式.
//      -除了存储数据的变量,所有的变量都是只可读的.(不要试着使用诸如'x'变量)
//
//  需要:
//      - JassHelper version 0.9.E.0 or newer (老版本也许仍能使用).
//
//  安装:
//      - 创建一个叫做"inkedList"的触发器.
//      - 转换成自定义代码并用这里的代码替换之.
//
//  Special Thanks:
//      - Rising_Dusk: helping me with the 1.1 code and idea
//      - Vexorian: giving me some hints about JassHelper
//      - Anitarf: convincing me that simpler is better
//
//==============================================================================
globals
//==============================================================================
// Change this value here to increase the number of avaliable links (see notes).
    private constant integer LINK_SIZE = 8190 // defualt 8190
//==============================================================================
endglobals
private keyword xnext
private keyword xprev
private keyword xparent
private keyword xfirst
private keyword xlast

struct Link[LINK_SIZE]
    integer data
    Link xnext
    Link xprev
    List xparent

    method operator next takes nothing returns Link
        return this.xnext
    endmethod
    method operator prev takes nothing returns Link
        return this.xprev
    endmethod
    method operator parent takes nothing returns List
        return this.xparent
    endmethod

    private static method createEmpty takes List parent, integer data returns Link
        local Link new = Link.allocate()
        set new.data = data
        set new.xparent = parent
        return new
    endmethod

    method insert takes integer data returns Link
        local Link new = Link.createEmpty(this.xparent, data)
        set new.xprev = this
        set new.xnext = this.xnext
        if this.xnext == 0 then
            set this.xparent.xlast = new
        else
            set this.xnext.xprev = new
        endif
        set this.xnext = new
        return new
    endmethod

    method insertBefore takes integer data returns Link
        local Link new = Link.createEmpty(this.xparent, data)
        set new.xprev = this.xprev
        set new.xnext = this
        if this.xprev == 0 then
            set this.xparent.xfirst = new
        else
            set this.xprev.xnext = new
        endif
        set this.xprev = new
        return new
    endmethod

    static method createBefore takes List l, integer data returns Link
        local Link new
        if l == 0 then
            debug call BJDebugMsg("Error: Cannot create Link for null List in Link.createBefore()")
            return 0
        endif
        if l.xfirst == 0 then
            set new = Link.createEmpty(l, data)
            set l.xfirst = new
            set l.xlast = new
            set new.xnext = 0
            set new.xprev = 0
            return new
        else
            return l.xfirst.insertBefore(data)
        endif
    endmethod

    static method create takes List l, integer data returns Link
        if l == 0 then
            debug call BJDebugMsg("Error: Cannot create Link for null List in Link.create()")
            return 0
        endif
        if l.xlast == 0 then
            return Link.createBefore(l, data)
        else
            return l.xlast.insert(data)
        endif
    endmethod
    method destroy takes nothing returns nothing
        if this.xparent == 0 then
            if this.xnext != 0 then
                set this.xnext.xparent = 0
                call this.xnext.destroy()
            endif
        else
            if this.xprev == 0 then
                set this.xparent.xfirst = this.xnext
            else
                set this.xprev.xnext = this.xnext
            endif
            if this.xnext == 0 then
                set this.xparent.xlast = this.xprev
            else
                set this.xnext.xprev = this.xprev
            endif
        endif
        set this.xnext = 0
        set this.xprev = 0
        set this.data = 0
        call this.deallocate()
    endmethod
endstruct

struct List
    Link xfirst
    Link xlast

    static method create takes nothing returns List
        local List new = List.allocate()
        set new.xfirst = 0
        set new.xlast = 0
        return new
    endmethod

    method operator first takes nothing returns Link
        return this.xfirst
    endmethod
    method operator last takes nothing returns Link
        return this.xlast
    endmethod
    method operator size takes nothing returns integer
        local Link n = this.xfirst
        local integer out = 0
        loop
            exitwhen n == 0
            set n = n.xnext
            set out = out + 1
        endloop
        return out
    endmethod

    method destroy takes nothing returns nothing
        if this.xfirst != 0 then
            set this.xfirst.xparent = 0
            call this.xfirst.destroy()
        endif
        set this.xfirst = 0
        set this.xlast = 0
        call this.deallocate()
    endmethod

    method clear takes nothing returns nothing
        if this.xfirst != 0 then
            set this.xfirst.xparent = 0
            call this.xfirst.destroy()
        endif
        set this.xfirst = 0
        set this.xlast = 0
    endmethod

    method search takes integer data returns Link
        local Link temp = this.xfirst
        loop
            exitwhen temp == 0
            if temp.data == data then
                return temp
            endif
            set temp = temp.xnext
        endloop
        return 0
    endmethod
endstruct

endlibrary
